It is useful in many information processing applications of computers to use multiple processors or multiple computers to speed up operations. Dividing a task and performing multiple processing and computing operations in parallel at the same time is known in the art, as are many systems and structures to accomplish this. An example is systolic array processing wherein a large information stream is divided up among rows of processors that perform sequential computations by column, and pass results to the next column. Other examples are found in the field of supercomputing, wherein multiple processors may be interconnected and tasks assigned to them in a number of different ways, and communication of intermediate results between processors and new data and instructions to them may be provided through crossbar switches, bus interconnection networks with or without routers, or direct interconnections between processors with message passing protocols such as MPICH, used on large machines.
Digital Signal Processing (DSP) is a pervasive technology, which is computationally burdened with Fast Fourier Transform (FFT) calculations, known as butterfly computations (also referred to as “butterflies”). The butterfly processing time has been and continues to be a major challenge to product advancements in applications such as wireless communications, due to the ever increasing speed and processing complexity requirements. Although prior art multiple processor architectures have improved the FFT processing speeds, those architectures have reached limitations to making further improvements because of physical constraints that limit the speed of exchanging information between computers. A novel approach to improve the butterfly computational speed is needed to take advantage of the new multiprocessor array architectures mentioned above. While the invention is described using a butterfly calculation, the invention is equally applicable to other complex calculations.